package org.xingole.jgit.lib;

import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * <p>Fast, efficient map for {@code ObjectId} subclasses in only one map.</p>
 * 
 * <p>In implementing layer, we choose the map structure to manage relationship between the object ids.
 * At the same time, remeber the entry of this map should be object id.</p>
 * 
 * <p>To use this map type, applications must have their entry value type extend from {@code ObjectIdOwnerMap.
 * Entry}, which itself extends from ObjectId class.</p>
 * 
 * <p>Git object instances can only be stored in <b>ONE</b> ObjectIdOwnerMap.</p>
 * 
 * <p>Every collection data structure in Java should provide the iterator to user so that they can 
 * walk the map to fetch their needed element efficently and more flexible.</p>
 * 
 * @param V - type of subclass of ObjectId that will be stored in the map. 
 * 
 * <p>We should notes user can custom theirselves ObjectId subclass to satisfy their service demand.</p>
 */
public class ObjectIdOwnerMap<V extends ObjectIdOwnerMap.Entry> 
                    implements Iterable<V>, ObjectIdSet{

    /******************************Some constants for the map****************************************/
    /**
     * <p>Size of the initial directory, will grow as necessary.</p>
     * 
     */
    private static final int INITIAL_DIRECTORY = 1024;

    /**
     * <p>Number of bits in a segment's index. Segments are 2^11 in size.</p>
     * 
     * <p>segment bits is used to evaluate the table length.</p>
     */
    private static final int SEGMENT_BITS = 11;

    /**
     * <p>The 32 bits w0 need to right shift SEGMENT_SHIFT bits to fetch the object table index.</p>
     */
    private static final int SEGMENT_SHIFT = 32 - SEGMENT_BITS;
    /**************************************The fields for map****************************************/
    /**
     * <p>Top level directory of the segments.</p>
     * 
     * <p>The low bits of the SHA-1 are used to select the segment from this directory.Each
     * segment is constant sized at 2^segment_bits.</p>
     * 
     * <b>How to understand the 2D array function:</b>
     * 
     * <p>JGit use the 2D matrix to implement the map data structure. </p>
     * 
     */
    V[][] directory;

    /**
     * <p>Total number of objects in this map.</p>
     * 
     * <p>Yeah, the collection should have the size field to stand for its space size.</p>
     * 
     * <p>Now, we haven't set the getter and setter methods, so set the field acess as packaged, 
     * namely default accessor.</p>
     */
    int size;

    /**
     * <p>The map doubles in capacity when {@code size} reaches this target.</p>
     * 
     * <p>oh! {@code grow} variable is the upper limit of the capacity of the map.
     * I think the grow maybe change with each map space reallocation. According the jgit, this 
     * map should double its capacity when the size of the map reaches the grow limit.</p>
     */
    private int grow;

    /**
     * <p>Number of low bits used to form the index into {@code directory}.</p>
     * 
     * TODO:  The function of bits variable?
     * 
     * <p>em...index is represented by binary number, then bits variables should be the bits of 
     * the index for the directory.</p>
     */
    int bits;

    /**
     * <p>Low bit mask to index into directory, 2^bits-1</p>
     * 
     * <p>Mask should vary from the bits, and its value is to set 1 for all bit.</p>
     */
    private int mask;

    /*************************************The constructors*******************************************/
    /**
     * Create an empty map.
     * 
     * <p>
     * In any map implementation, the default constructor should be considered carefully, because 
     * empty collection is on demand in the normalized problems.</p>
     */
    public ObjectIdOwnerMap() {
       bits = 0;
       mask  = 0;
       grow = computeGrowAt(bits);

       // To create the basic null directory.
       directory = (V[][]) new Entry[INITIAL_DIRECTORY][];
       directory[0] = newSegment();
    }

    private static final int computeGrowAt(int bits) {
        return 1 << (bits + SEGMENT_BITS);
    }

    private final V[] newSegment() {
        // This method only is used to evaluates the jgit each segment size.
        return (V[]) new Entry[1 << SEGMENT_BITS];
    }

    /***************************The operation for common map****************************************/
    /**
     * Remove all entries from this map.
     */
    public void clear() {
        // reset the size of the map to zero.
        size = 0;

        for(V[] tbl : directory) {
            if(tbl == null)  // It means no more segment after current one. 
                break;
            Arrays.fill(tbl, null); // Implements by the JDK API.
        }
    }

    /**
     * Lookup an existing mapping.
     * @param toFind - the object identifier to find.
     * @return the instance mapped to toFind, or null if no mapping exists.
     */
    public V get(final AnyObjectId toFind) {
        int h = toFind.w0;    // jgit use lower w field in AnyObjectId to fetch index.
        V obj = directory[h & mask][h >>> SEGMENT_SHIFT];

        // then, traveling the linklist for the entry.
        for(; obj != null; obj = (V) obj.next) {
            if(AnyObjectId.equals(obj, toFind))
                return obj;
        }
        return null;
    } 

    /**
     * Returns true if this map contains the specified object.
     * @param objectId - object to find.
     * @return true if the mapping exists for this object; false otherwise.
     */
    @Override
    public boolean contains(final AnyObjectId objectId) {
        return get(objectId) != null;
    }

    /**
     * Store an object for future lookup.
     * 
     * <p>An existing mapping for <b>must not</b> be in this map. oh! This method only allows to
     * add new mapping not the existing mapping. Therefore, callers must first call get(AnyObjectId)
     * to verify there is no current mapping prior to adding a new mapping, otherwise using 
     * <code>addIfAbsent</code> method.</p>
     * @param <Q>
     * @param newValue - the object id to store.
     */
    public <Q extends V> void add(final Q newValue) {
        if(++size == grow) 
            grow();      // The capacity for this map is not enough, so adjust the map.
        
        int h = newValue.w0;  // AnyObjectId w0 is used to calculate the element index.
        V[] table = directory[h & mask];  // oh! w0 field is used to fetch directory index.

        h >>>= SEGMENT_SHIFT;  

        /*
         *  Implementation notes: w0 field's function
         *                                       1:masking to fetch directory index
         *        MSB                 SEGMENT_SHIFT       ||      LSB  
         *      ---|--------------------|---------|-------1-------|----
         *       w0_31  w0_30   ...   w0_21... w0_b  ...  w0_1   w0_0
         *      --|-----------2---------|--------|-----bits-------|----
         *          2: right shift to fetch table index                     
         */
        // insert the current object => using linklist operation
        // insert from the beginning of the linklist.
        newValue.next = table[h];
        table[h] = newValue;
    }

    /**
     * Store an object for future lookup.
     * 
     * <p>Stores <code>newValue</code>, but only if there is not already an object for the same
     * object name.Callers can tell if the value is new by checking the return value with reference
     * equality:</p>
     * 
     * <pre>
     *      V obj = ...;
     *      boolean wasNew = map.addIfAbsent(obj) == obj;
     * </pre>
     * @param <Q>
     * @param newValue - the object to store.
     * @return newValue if stored, or the prior value already stored and that would have been returned 
     * had the caller used get(newValue) first.
     */
    @SuppressWarnings("unchecked")
    public <Q extends V> V addIfAbsent(final Q newValue) {
        int h = newValue.w0;
        V[] table = directory[h & mask];
        h >>>= SEGMENT_SHIFT;

        // traveling the linklist.
        for(V obj = table[h]; obj != null; obj = (V) obj.next) {
            if(AnyObjectId.equals(obj, newValue))  // em... according the condition, we should create new equals methods
                return obj;
        }

        // no existing so need to add this new value to the map.
        if(++size == grow)
            grow();
        
        newValue.next = table[h];
        table[h] = newValue;

        return newValue;
    }

    private void grow() { // dynamically adjust the capacity of the map.  
        // the length of the directory before adjusting the capacity      
        final int oldDirLen = 1 << bits;  
        final int s = 1 << bits;
        
        // the new length of the directory should be double the old length.
        // nlen = 2 * olen = olen << 1. Now, let bit increments.
        bits++;  
        mask = (1 << bits) - 1;  // TODO: why (1 << bits) need to minus 1.
        grow = computeGrowAt(bits);

        /*
         * Implementation Notes: expand the directory
         * 
         * 1. Quadruple(4 times) the dirctory if it needs to expand. 
         * 2. Expanding the directory is expensive because it generates garbage, so try to
         * avoid doing it often.
         * 
         * Recommend to try your best not to call this method frequently.
         */

         final int newDirLen = 1 << bits;
         if(directory.length < newDirLen) {
            V[][] newDir = (V[][]) new Entry[newDirLen << 1][];
            System.arraycopy(directory, 0, newDir, 0, oldDirLen);
            directory = newDir;
         }

         /* 
          *  Implementation Note: expand the table capcity
          *  
          * For every bucket of every old segment, split the chain between the old
          *  segment and the new segment's corresponding bucket. To select between them 
          *  use the lowest bit that was just added into the mask above. This causes the 
          * table to double in capacity.
          */
          for(int dirIdx = 0; dirIdx < oldDirLen; dirIdx++) {
            final V[] oldTable = directory[dirIdx];
            final V[] newTable = newSegment();

            for(int i = 0; i < oldTable.length; i++) {
                V chain0 = null;
                V chain1 = null;
                V next;

                for (V obj = oldTable[i]; obj != null; obj = next) {
                    next = (V) obj.next;

                    if((obj.w0 & s) == 0) {  // TODO: why the selection strategy is used here?
                        obj.next = chain0;
                        chain0 = obj;
                    } else {
                        obj.next = chain1;
                        chain1 = obj;
                    }
                }

                oldTable[i] = chain0;
                newTable[i] = chain1;
            }
            directory[oldDirLen + dirIdx] = newTable;
          }
    }

    /**
     * 
     * @return number of objects in this map
     */
    public int size() {
        return size;
    }

    /**
     * 
     * @return true is size() is 0;
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**********************The internal iterator of this map*************************************/
    @Override
    public Iterator<V> iterator() {
        return new Iterator<V>() {  // Here, jgit uses the class expression for iterator pattern.
            private int found;   // found can be understand as the iterative rounds.
            private int dirIdx;
            private int tblIdx;
            private V next;     // the next entry in linklist.

            /*
             * Implementation Note:
             * 
             * The map structure:
             *       j       0                1                        j=>tblIdx                                 n => the existing entry tatal in the table => 1 << SEGMENT_BITS    
             *      -----------------------------------------------------------------------------------------------             i
             *      ||  entry_0,0  |  | entry_0,1 |    ...  | entry_0,j |  |  entry_0,j+1 |  ...  | entry_0,n-1  ||             0
             *      --------------------------------------------------------------------------------------------
             *      ||  entry_1,0  |  | entry_1,1 |    ...  | entry_1,j |  |  entry_1,j+1 |  ...  | entry_1,n-1  ||             1
             *      --------------------------------------------------------------------------------------------------------
             *                                         ....      i=>dirIdx ,j=>tblIdx
             *      --------------------------------------------------|-----------------------------------------------------
             *      ||  entry_i,0  |  | entry_i,1 |    ...  | entry_i,j |  |  entry_i,j+1 |  ...  | entry_i,n-1  ||             i => dirIdx
             *      -------------------------------------------------|------------------------------------------------------
             *                                         ....        found = i * n + j   
             *      ---------------------------------------------------------------------------------------------------------
             *      ||  entry_m-1,0  |  | entry_m-1,1 |    ...  | entry_m-1,j |  |  entry_m-1,j+1 |  ...  | entry_m-1,n-1  ||   m => the capacity of the directory => 1 << bits
             *      --------------------------------------------------------------------------------------------------------- 
             *                    every row represents the complete table, and a table represents the jgit segment.
             *   
             * 
             *      Notes that the last entry of each table has null next entry, so the next field of the entry node is null value.
             *      1. size is the total of the entry in the directory, viewing the whole structure as 3D mode.
             *      2. found is the sequence number of the traveled entry.
             *      3. what's more, please remeber every entry in array should is first node of the entry linklist structure.
             *                    element in directory
             *                        |        next
             *       linklist:   entry_i, j, 0 -> entry_i, j, 1 -> ... entry_i, j, n - 1 -> null
             * 
             *      The loop invariation:
             *             1. all entries whose coordinate (i, j) is such that i in [0, dirIdx - 1], j in [0, tblIdx - 1] have be travelled.
             *             2. next() method in iterator is to fetch the current coordinate entry object => Git object id.
             */

            @Override
            public boolean hasNext() {
                return found < size;
            }

            @Override
            public V next() {
                if(next != null)       // iterates the node in the linklist.  
                    return found(next);
                
                // iterates the 2D array next entry.
                for(; ; ) {
                    V[] table = directory[dirIdx];
                    if(tblIdx == table.length) {
                        if(++dirIdx >= (1 << bits))     // 1 << bits => m  Here, jgit use the binary operator is improve the code efficience.
                            throw new NoSuchElementException();
                        table = directory[dirIdx];
                        tblIdx = 0;
                    }

                    while(tblIdx < table.length) {
                        V v = table[tblIdx++];
                        if(v != null)
                            return found(v);
                    }
                }
            }
            
            private V found(V v) {
                found++;
                next = (V) v.next;
                return v;
            }

            @Override
            public void remove() {
                // This map implementation mustn't remove the current entry => immutable map structure.
                throw new UnsupportedOperationException();
            }
        };
    }

    /**
     * <p>Type of entry stored in the {@code ObjectIdOwnerMap}.</p>
     * 
     * <p>When we fist design the map implementing class, the entry of this map should be considered 
     * first carefully. Usually, the entry is designed as the internal class for this map.</p>
     * 
     * <p>we can think of this convention as a kind of Java design pattern.</p>
     * 
     */
    public static abstract class Entry extends ObjectId {
        // em...This map may be implemented by the similar hash map algorithms. 
        // So... the entry should process the reference pointed to next entry.
        transient Entry next;

        /**
         * Initialize this entry with a specific ObjectId.
         * @param id - the id the entry represents.
         */
        public Entry(AnyObjectId id) {
            super(id);
        }
    }
}
